/*
 * @lc app=leetcode.cn id=697 lang=cpp
 *
 * [697] 数组的度
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;

class Solution
{
    struct Info
    {
        int label;
        int x0, x1;
        int cnt;
        Info() : x0(-1), x1(-1), cnt(0) {}
    };

public:
    int findShortestSubArray(vector<int> &nums)
    {
        vector<Info> infos(50000);
        for (int i = 0; i < nums.size(); i++)
        {
            auto &info = infos[nums[i]];
            info.cnt++;
            info.label = nums[i];
            if (info.x0 == -1)
            {
                info.x0 = i;
            }
            info.x1 = i;
        }
        sort(infos.begin(), infos.end(), [](Info &l, Info &r) -> bool
             { return l.cnt < r.cnt; });
        const int maxcnt = (infos.end()-1)->cnt;
        int ans = (infos.end()-1)->x1 - (infos.end()-1)->x0 + 1;
        for(auto it = infos.end() - 1; it >= infos.begin(); it--)
        {
            if(maxcnt != it->cnt) break;
            ans = std::min(ans, it->x1 - it->x0 + 1);
        }
        return ans;
    }
};
// @lc code=end
